package org.bear.linkList;

import java.util.HashMap;
import java.util.Map;

/*
146. LRU 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */
public class LRUCache {
    Map<Integer, Node> preNodeMap = null;
    int sizeLimit = 0;
    Node head = new Node(-1, -1);
    Node tail = head;

    private static class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }


    public LRUCache(int capacity) {
        sizeLimit = capacity;
        preNodeMap = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node node = preNodeMap.get(key);
        if(node == null){
            return -1;
        }
        // 节点移动到末尾
        preNodeMap.put(key, tail);
        tail.next = node.next;
        tail = tail.next;
        node.next = node.next.next;
        preNodeMap.put(node.next.key, node);
        tail.next = null;
        return tail.value;
    }

    public void put(int key, int value) {
        if (preNodeMap.size() == sizeLimit && !preNodeMap.containsKey(key)) {
            // 移除最久未用
            if (sizeLimit==1){
                preNodeMap.clear();
                head.next = null;
                tail = head;
            }else {
                preNodeMap.remove(head.next.key);
                head.next = head.next.next;
                preNodeMap.put(head.next.key, head);
            }
        }
        if (preNodeMap.containsKey(key)) {
            // 链表移除
            Node preNode = preNodeMap.get(key);
            preNode.next = preNode.next.next;
            if (preNode.next!=null){
                preNodeMap.put(preNode.next.key, preNode);
            }else {
                tail = preNode;
            }
        }
        preNodeMap.put(key, tail);
        tail.next = new Node(key, value);
        tail = tail.next;
    }


    public static void main(String[] args) {
//        ["LRUCache","get","put","get","put","put","get","get"]
//       [[2],[2],[2,6],[1],[1,5],[1,2],[1],[2]]
        LRUCache lruCache = new LRUCache(2);
        lruCache.get(2);
        lruCache.put(2, 6);
        lruCache.get(1);
        lruCache.put(1, 5);
        lruCache.put(1, 2);
        lruCache.get(1);
        lruCache.get(2);
    }


}
